package com.rom.stack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 中缀转后缀并计算
 * 逆波兰计算器 ( 后缀表达式 )
 */
public class PolandNotation {

    public static void main(String[] args) {

//        String suffixExpression = "3 5 2 * + 6 - 4 +";
//        List<String> listString = getListString(suffixExpression);
//        System.out.println(PolandNotation.calculate(listString));

        String expression = "12+((2+3)*4)-5";

        String[] split = expression.split("");
        System.out.println(Arrays.asList(split));

        List<String> toInfixExpress = toInfixExpressionList(expression);
        System.out.println(toInfixExpress);
        List<String> parseSuffixExpress = parseSuffixExpreesionList(toInfixExpress);
        System.out.println(parseSuffixExpress);

        System.out.println(calculate(parseSuffixExpress));

    }

    public static List<String> getListString(String suffixExpression){
        String[] strings = suffixExpression.split(" ");
        List<String> list = new ArrayList<>();
        for (String ele:strings) {
            list.add(ele);
        }
        return list;
    }

    /**
     * 字符串转化成中缀表达式
     * @param s
     * @return
     */
    public static List<String> toInfixExpressionList(String s){

        ArrayList<String> arrayList = new ArrayList();
        int index = 0;  //字符串的索引
        String str; //多位数字
        char ch;
        while (index < s.length()){
            if((ch = s.charAt(index)) < 48 || (ch = s.charAt(index))>57){
                //ch为字符
                arrayList.add(String.valueOf(ch));
                index++;
            }else{
                //不为字符时
                str = "";
                while (index < s.length() && (ch = s.charAt(index)) >= 48 && (ch = s.charAt(index))<=57){
                    str += ch;
                    index++;
                }
                arrayList.add(str);
            }
        }
        return arrayList;
    }
    /**
     * 中缀转后缀
     * @param list
     * @return
     */
    public static List<String> parseSuffixExpreesionList(List<String> list){
//        [1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
        Stack<String> s1 = new Stack<>();
        ArrayList<String> s2 = new ArrayList<>();
        for (String item : list) {
//            if(item.charAt(0)>=48 && item.charAt(0)<=57){
//                //表示数字，直接入栈
//                s2.add(item);
//            }else{
//                //字符的话   先判断是什么字符
//
//
//            }
            if(item.matches("\\d+")){
                s2.add(item);
            }else if(item.equals("(")){
                s1.push(item);
            }else if(item.equals(")")){
                //
                while(!s1.peek().equals("(")){
                    //查看栈顶如果不是（   则加入栈中
                    s2.add(s1.pop());
                }
                //删除s1栈中的 （
                s1.pop();
            }else{
                //s1的栈不为空  且item的优先级 <= 栈顶；
                while (s1.size() != 0 && Operation(item) <= Operation(s1.peek())){
                    s2.add(s1.pop());
                }
//                item入栈
                s1.push(item);
            }
        }
        while (s1.size()!=0){
            s2.add(s1.pop());
        }
        return s2;
    }

    /**
     * 返回运算符的优先级
     * @param ch
     * @return
     */
    public static int  Operation(String ch){

        switch (ch){
            case "+":
            case "-":
                return 1;
            case "*":
            case "/":
                return 2;
            case "(":
                    return 0;
            default:
                throw  new RuntimeException("运算符异常");
        }
    }

    /**
     * @param list
     * @return
     */

    public static String calculate(List<String> list){
        Stack<String> stack = new Stack<>();
        for (String s : list) {
            if(s.matches("\\d+")){
                stack.push(s);
            }else{
                //如果是符号，弹出计算
               int num2 =  Integer.parseInt(stack.pop());
               int num1 =  Integer.parseInt(stack.pop());
               int res = 0;
                if("+".equals(s)){
                    res = num2 + num1;
                }else if("-".equals(s)){
                    res = num1 - num2;
                }else if("*".equals(s)){
                    res = num1 * num2;
                }else if("/".equals(s)){
                    res = num1 / num2;
                }else{
                    throw new RuntimeException("运算符有误");
                }
                //计算后入栈
                stack.push(String.valueOf(res));
            }
        }
        return stack.pop();
    }
}

